#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef int ElemType;
typedef struct node{
  ElemType data;
  struct node *next;
}Node;

//初始化虚拟头节点
Node* initList(){
  Node *head =(Node*)malloc(sizeof(Node));
  head->data=0;
  head->next=NULL;
  return head;
}

//遍历链表
void listNode(Node* L){
  Node *p=L->next;
  while(p!=NULL){
    printf("%d ",p->data);
    p=p->next;
  }
  printf("\n");
}

//头插法:插入在虚拟头节点后
int insertHead(Node* L,ElemType e){
  Node *p=(Node*)malloc(sizeof(Node));
  p->data=e;
  p->next=L->next;
  L->next=p;
  return 1;
}

//获取尾节点地址
Node* get_tail(Node *L){
  Node *p=L;
  while(p->next!=NULL){
    p=p->next;
  }
  return p;
}
//尾插法:插入在链表尾部
int insertTail(Node* L,ElemType e){
  Node *p=(Node*)malloc(sizeof(Node));
  p->data=e;
  p->next=NULL;
  Node *temp=get_tail(L);
  temp->next=p;
  return 1;
}

//获取坐标节点的前一个节点
Node* getIndex(Node* L,int pos){
  int i=0;
  Node *p=L;
  while(i++<pos-1){
    p=p->next;
    if(p==NULL) return NULL;
  }
  return p;
}

//指定位置插入:
int insertNode(Node* L,int pos,ElemType e){
  Node *p=getIndex(L,pos);
  if(p==NULL) return 0;
  Node *q=(Node*)malloc(sizeof(Node));
  q->next=p->next;
  q->data=e;
  p->next=q;
  return 1;
}

//删除节点
int deleteNode(Node* L,int pos){
  Node* p=getIndex(L,pos);
  if(p==NULL||p->next==NULL){
    printf("非法坐标!\n");
    return 0;}
  Node *q=p->next;
  p->next=q->next;
  free(q);
  return 1;
}

//获取链表长度
int getLength(Node* L){
  int len=0;
  Node *p=L;
  while(p->next!=NULL){
    len++;
    p=p->next;
  }
  return len;
}

//释放链表(头节点不释放
int freeList(Node* L){
  Node* p=L->next;
  Node* q;
  while(p!=NULL){
    q=p->next;
    free(p);
    p=q;
  }
  L->next=NULL;
  return 1;
}

int findNodeFS(Node* L,int k){
  if(getLength(L)<k) return 0;
  Node *fast=L,*slow=L;
  for(int i=0;i<k;i++){
    fast=fast->next;
  }
  while(fast->next!=NULL){
    fast=fast->next;
    slow=slow->next;
  }
  printf("倒数第%d个节点的存储值为:%d",k,slow->next->data);
  return 1;
}

Node* findIntersectionNode(Node* headA,Node* headB){//返回相同的后缀头节点
  if(headA==NULL||headB==NULL) return NULL;
  int lenA=getLength(headA);
  int lenB=getLength(headB);
  int n=lenA-lenB;
  Node *fast,*slow;
  if(n<0){
    fast=headB;
    slow=headA;
    n=abs(n);
  }else{
    fast=headA;
    slow=headB;
  }
  for(int i=0;i<n;i++){
    fast=fast->next;
  }
  while(fast!=slow){
    fast=fast->next;
    slow=slow->next;
  }
  return fast;
}

//删除绝对值相同的节点
void removeNode(Node* L){
  int index,len=getLength(L);
  int *q=(int*)malloc(sizeof(int)*(len+1));
  for(int i=0;i<=len;i++){
    q[i]=0;
    //*(q+i)=0 与之等价
  }
  Node *p=L;
  while(p->next!=NULL){
    index=abs(p->next->data);
    if(q[index]==0){
      q[index]=1;
      p=p->next;
    }else{
      Node *temp=p->next;
      p->next=temp->next;
      free(temp);
    }
  }
  free(q);
}

//反转链表
Node* reverseList(Node* L){
  // if(L==NULL||L->next==NULL) return L;
  // Node *pre=NULL,*cur=L->next,*nxt=cur->next;
  // while(cur!=NULL){
  //   cur->next=pre;
  //   pre=cur;
  //   cur=nxt;
  //   if(nxt!=NULL) nxt=nxt->next;
  // }
  // L->next=pre;
  // return L;
  Node *first=NULL,*second=L->next,*third;
  while(second!=NULL){
    third=second->next;
    second->next=first;
    first=second;
    second=third;
  }
  L->next=first;
  return L;
}

//删除链表的中间节点
Node* delMiddleNode(Node* L){
  Node *slow=L->next,*fast=L->next,*ss=L;
  while(fast!=NULL&&fast->next!=NULL){
    fast=fast->next->next;
    slow=slow->next;
    ss=ss->next;
  }
  // Node *temp=slow->next;
  printf("%d\n",slow->data);
  ss->next=slow->next;
  free(slow);
  return L;
}

//排序:使得123456->162534
Node* reOrderList(Node* L){
  Node *fast=L,*slow=L;
  while(fast!=NULL&&fast->next!=NULL){
    fast=fast->next->next;
    slow=slow->next;
  }
  Node *pre=NULL,*cur=slow->next,*nxt=NULL;
  slow->next=NULL;
  while(cur!=NULL){
    nxt=cur->next;
    cur->next=pre;
    pre=cur;
    cur=nxt;
  }
  Node *p1=L->next,*p2,*q1=pre,*q2;
  while(p1!=NULL&&q1!=NULL){
    p2=p1->next;
    p1->next=q1;
    q2=q1->next;
    q1->next=p2;
    p1=p2;
    q1=q2;
  }
  return L;
}

//判断是否成环
int isCycle(Node* L){
  Node *fast=L,*slow=L;
  while(fast!=NULL&&fast->next!=NULL){
    fast=fast->next->next;
    slow=slow->next;
    if(fast==slow) return 1;
  }
  return 0;
}

Node* findCycleBegin(Node* L){
  if(isCycle(L)==0) return NULL;
  Node *fast=L,*slow=L;
  while(fast!=NULL&&fast->next!=NULL){
    fast=fast->next->next;
    slow=slow->next;
    if(fast==slow) break;
  }

  int count=1;
  while(fast->next!=slow){
    fast=fast->next;
    count++;
  }

  fast=L,slow=L;
  for(int i=0;i<count;i++){
    fast=fast->next;
  }
  while(fast!=slow){
    fast=fast->next;
    slow=slow->next;
  }
  return slow;
}

int main(){
  Node *list = initList();
		
	insertTail(list, 1);
	insertTail(list, 2);
	insertTail(list, 3);
  
  Node *three=getIndex(list,3)->next;
	insertTail(list, 4);
	insertTail(list, 5);
	insertTail(list, 6);
	insertTail(list, 7);
	insertTail(list, 8);
  Node *eight=getIndex(list,8)->next;
	eight->next=three;
  Node *p=findCycleBegin(list);
  printf("%d\n",p->data);

  // listNode(list);
  return 0;
}